package heepstackqueue;

import java.util.ArrayList;
import java.util.Stack;

// 中位数
// 方法一：常规方法，每次进行排序后获取中位数
public class D230725 {
    ArrayList<Integer> list = new ArrayList<>();
    public void Insert(Integer num) {
        list.add(num);
    }
    public Double GetMedian() {
        list.sort((o1, o2) -> {
            return o1 - o2;
        });
        int n = list.size();
        if (n % 2 == 0) {
            return (list.get(n / 2) + list.get(n / 2 - 1)) / 2.0;
        } else {
            return list.get(n / 2) * 1.0;
        }
    }
}
// 中位数
// 方法二：
// 本题是插入一个数，获取一次中位数
// 如果每次获取中位数时，都进行排序，效率较低
// 可以在插入时，使用插入排序
class Solution2 {
    ArrayList<Integer> list = new ArrayList<>();
    public void Insert(Integer num) {
        // 从前往后，到最后都没找到插入位置，就放到最后
        int i = 0;
        for (; i < list.size(); i++) {
            if (num <= list.get(i)) {
                break;
            }
        }
        // 插入 num，i 之后的数后移一格
        list.add(i, num);
    }
    public Double GetMedian() {
        int n = list.size();
        if (n % 2 == 0) {
            return (list.get(n / 2) + list.get(n / 2 - 1)) / 2.0;
        } else {
            return list.get(n / 2) * 1.0;
        }
    }
}


// 表达式求值
class Solution3 {
    public int solve (String s) {
        ArrayList<Integer> res = function(s, 0);
        return res.get(0);
    }
    public ArrayList<Integer> function(String s, int index){
        Stack<Integer> stack = new Stack<Integer>();
        int num = 0;    // 记录当前数字
        char op = '+';  // 记录当前数字前面的符号
        int i;          // 记录当前的下标
        for(i = index; i < s.length(); i++){

            // 遇到数字，将一串数字转为 int
            if(s.charAt(i) >= '0' && s.charAt(i) <= '9'){
                num = num * 10 + s.charAt(i) - '0';
                if(i != s.length() - 1)
                    continue;
            }

            // 碰到'('时，把整个括号内的当成一个数字处理
            if(s.charAt(i) == '('){
                // 递归处理括号
                ArrayList<Integer> res = function(s, i + 1);
                num = res.get(0);   // 得到括号中计算后的数字
                i = res.get(1);     // 得到当前遍历到的位置
                if(i != s.length() - 1)
                    continue;
            }

            switch(op){
                //加减号先入栈
                case '+':
                    stack.push(num);
                    break;
                case '-':
                    //相反数
                    stack.push(-num);
                    break;
                //优先计算乘号
                case '*':
                    int temp = stack.pop();
                    stack.push(temp * num);
                    break;
            }

            num = 0;
            //右括号结束递归
            if(s.charAt(i) == ')')
                break;
            else
                op = s.charAt(i);
        }
        int sum = 0;
        //栈中元素相加
        while(!stack.isEmpty())
            sum += stack.pop();
        ArrayList<Integer> temp = new ArrayList<Integer>();
        temp.add(sum);
        temp.add(i);
        return temp;
    }
}